import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();

    }
// 原始错误代码
//    public int findMaxValueOfEquation(int[][] points, int k) {
//        /**
//         * 满足不等式的最大值
//         * */
//        // 1 预处理
//        int n = points.length;
//        int maxSum = -0x3f3f3f3f;
//
//        // 2 使用单调队列遍历（队列中始终维持可能匹配项）
//        Deque<int[]> queue = new LinkedList<>();
//        for(int i = 0; i < n; i++) {
//            // -维护队头x始终有效
//            while(!queue.isEmpty() && points[i][0] - queue.peekFirst()[0] > k) {
//                queue.pollFirst();
//            }
//            // -更新最大值（此处感觉有问题，时间复杂度会很高）
//            for(int[] e: queue) {
//                maxSum = Math.max(points[i][0] - e[0] + points[i][1] + e[1], maxSum);
//            }
//            // -入队
//            queue.offerLast(points[i]);
//        }
//
//        // 3 返回值
//        return maxSum;
//    }
    public int findMaxValueOfEquation(int[][] points, int k) {
        /**
         * 满足不等式的最大值
         * */
        // 1 预处理
        int n = points.length;
        long maxSum = -0x3f3f3f3f;

        // 2 使用单调队列遍历（队列中始终维持可能匹配项）
        Deque<long[]> queue = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            long curSub = points[i][1] - points[i][0];
            // -维护队头x始终有效
            while(!queue.isEmpty() && points[i][0] - queue.peekFirst()[0] > k) {
                queue.pollFirst();
            }
            // -更新最大值（优化后）
            if(!queue.isEmpty()) {
                maxSum = Math.max(maxSum, queue.peekFirst()[2] + points[i][0] + points[i][1]);
            }
            // -入队
            while(!queue.isEmpty() && queue.peekLast()[2]<= curSub) {
                queue.pollLast();
            }
            queue.offerLast(new long[]{points[i][0], points[i][1], points[i][1] - points[i][0]});
        }

        // 3 返回值
        return (int)maxSum;
    }
}
